package com.icbc.DataStructuresAndAlgorithms;

/**
 * 二叉树
 */
public class TreeDomo {
	public static void main(String[] args) {
		
		
		/*HeroTree tree = new HeroTree();
		HeroTree.HeroNode root = tree.new HeroNode(4, "王伟");
		HeroTree.HeroNode node2 = tree.new HeroNode(2,"李玲");
		HeroTree.HeroNode node3 = tree.new HeroNode(6,"阿南");
		HeroTree.HeroNode node4 = tree.new HeroNode(1,"灵兽");
		HeroTree.HeroNode node5 = tree.new HeroNode(3,"寒烟");
		HeroTree.HeroNode node6 = tree.new HeroNode(5,"南陵");
		HeroTree.HeroNode node7 = tree.new HeroNode(7,"烟雨");*/
		LineHeroTree tree = new LineHeroTree();
		LineHeroTree.HeroNode root = tree.new HeroNode(4, "王伟");
		LineHeroTree.HeroNode node2 = tree.new HeroNode(2,"李玲");
		LineHeroTree.HeroNode node3 = tree.new HeroNode(6,"阿南");
		LineHeroTree.HeroNode node4 = tree.new HeroNode(1,"灵兽");
		LineHeroTree.HeroNode node5 = tree.new HeroNode(3,"寒烟");
		LineHeroTree.HeroNode node6 = tree.new HeroNode(5,"南陵");
		LineHeroTree.HeroNode node7 = tree.new HeroNode(7,"烟雨");
		root.setLeft(node2);
		root.setRight(node3);
		node2.setLeft(node4);
		node2.setRight(node5);
		node3.setLeft(node6);
		node3.setRight(node7);
		tree.setRoot(root);
		
		//线索化二叉树
		tree.toLineTree(tree.getRoot(),0);
		
		tree.listLineTreeQian();
		System.out.println();
		//前: 4 2 1 3 6 5 7
		//中: 1 2 3 4 5 6 7
		//后: 1 3 2 5 7 6 4
		System.out.println(node4.getLeft());
		System.out.println(node4.getRight());
		System.out.println(node5.getLeft());
		System.out.println(node5.getRight());
		System.out.println(node6.getLeft());
		System.out.println(node6.getRight());
		System.out.println(node7.getLeft());
		System.out.println(node7.getRight());
		
		/*//删除
		tree.del(8);
		//遍历
		tree.listq('h');
		//查询
		System.out.println(tree.find(tree.getRoot(), 0));
		//将数组看做二叉树进行遍历
		int[] arr = {4,2,6,1,3,5,7};
		listArrayHou(arr,0);*/
	}
	
	/*
	 * index是数组的下标,此数组与二叉树对应
	 * 在数组中第n个元素的左子节点索引为2 * n + 1
	 * 在数组中第n个元素的右子节点索引为2 * n + 2
	 * 在数组中第n个元素的父节点索引为(n - 1) / 2
	 */
	//将数组当成二叉树进行前序遍历
	public static void listArrayQian(int[] arr,int index){
		//判断为空树的话直接跳过
		if (arr == null || arr.length == 0){
			System.out.println("空树");
			return;
		}
		//打印节点
		System.out.println(arr[index]);
		//判断索引不能越界,进行左递归
		if (2 * index + 1 < arr.length){
			listArrayQian(arr,2 * index + 1);
		}
		//判断索引不能越界,进行右递归
		if (2 * index + 2 < arr.length){
			listArrayQian(arr,2 * index + 2);
		}
	}
	
	//将数组当成二叉树进行中序遍历
	public static void listArrayZhong(int[] arr,int index){
		//判断为空树的话直接跳过
		if (arr == null || arr.length == 0){
			System.out.println("空树");
			return;
		}
		//判断索引不能越界,进行左递归
		if (2 * index + 1 < arr.length){
			listArrayZhong(arr,2 * index + 1);
		}
		//打印节点
		System.out.println(arr[index]);
		//判断索引不能越界,进行右递归
		if (2 * index + 2 < arr.length){
			listArrayZhong(arr,2 * index + 2);
		}
	}
	
	//将数组当成二叉树进行后序遍历
	public static void listArrayHou(int[] arr,int index){
		//判断为空树的话直接跳过
		if (arr == null || arr.length == 0){
			System.out.println("空树");
			return;
		}
		//判断索引不能越界,进行左递归
		if (2 * index + 1 < arr.length){
			listArrayHou(arr,2 * index + 1);
		}
		//判断索引不能越界,进行右递归
		if (2 * index + 2 < arr.length){
			listArrayHou(arr,2 * index + 2);
		}
		//打印节点
		System.out.println(arr[index]);
	}
}

//普通无序二叉树
class HeroTree{
	private HeroNode root;
	
	public void add(int id,String name){
		HeroNode node = new HeroNode(id, name);
		if (root == null){
			root = node;
		}else{
			addNode(root,node);
		}
	}
	
	private void addNode(HeroNode root,HeroNode node){
		
		if (root.getId() > node.getId()){
			if (root.getLeft() != null)
				addNode(root.getLeft(),node);
			else
				root.setLeft(node);
		} else {
			node.setLeft(this.root);
		}
	}
	
	/*
	 * 这里的二叉树遍历思路与向下面的相同,但区别在于节点
	 * 内部遍历和外部遍历
	 */
	//前序遍历
	public void listqian(HeroNode temp){
		if (temp == null){
			return;
		}
		System.out.println(temp);
		listqian(temp.getLeft());
		listqian(temp.getRight());
	}
	//中序遍历
	public void listzhong(HeroNode temp){
		if (temp != null){
			listzhong(temp.getRight());
			System.out.println(temp);
			listzhong(temp.getLeft());
		}
	}
	//后序遍历
	public void listhou(HeroNode temp){
		if (temp != null){
			listhou(temp.getLeft());
			listhou(temp.getRight());
			System.out.println(temp);
		}
	}
	
	//此查找时有序二叉树查找
	public HeroNode find(HeroNode temp,int id){
		if (temp == null){
			return null;
		}
		if (temp.getId() > id){
			return find(temp.getLeft(),id);
		}else if (temp.getId() < id){
			return find(temp.getRight(),id);
		}else{
			return temp;
		}
	}
	
	/*
	 *
	 */
	//前序查找
	public HeroNode findqian(HeroNode temp,int id){
		if (temp == null || temp.getId() == id){
			return temp;
		}
		HeroNode heroNode = null;
		heroNode = findqian(temp.getLeft(), id);
		if (heroNode != null){
			return heroNode;
		}
		heroNode = findqian(temp.getRight(), id);
		return heroNode;
	}
	//中序查找
	public HeroNode findzhong(HeroNode temp,int id){
		if (temp == null){
			return temp;
		}
		HeroNode heroNode = null;
		heroNode = findzhong(temp.getLeft(), id);
		if (temp.getId() == id){
			return temp;
		}
		if (heroNode != null){
			return heroNode;
		}
		heroNode = findzhong(temp.getRight(), id);
		return heroNode;
	}
	
	//后序查找
	public HeroNode findhou(HeroNode temp,int id){
		if (temp == null){
			return temp;
		}
		HeroNode heroNode = null;
		heroNode = findhou(temp.getLeft(), id);
		if (heroNode != null){
			return heroNode;
		}
		heroNode = findhou(temp.getRight(), id);
		if (temp.getId() == id){
			return temp;
		}
		return heroNode;
	}
	
	
	//节点内遍历方法
	public void listq(char type){
		if (root != null) {
			if (type == 'q') {
				root.listqian();
			} else if (type == 'z') {
				root.listzhong();
			} else {
				root.listhou();
			}
		}
	}
	//节点内查询方法
	public HeroNode find(char type,int id){
		if (root != null) {
			if (type == 'q') {
				return root.findqian(id);
			} else if (type == 'z') {
				return root.findzhong(id);
			} else {
				return root.findhou(id);
			}
		}
		return null;
	}
	
	public void del(int id){
		if (root == null){
			System.out.println("空树");
		} else if (root.getId() == id){
			root = null;
		} else {
			root.del(id);
		}
	}
	
	public HeroNode getRoot() {
		return root;
	}
	
	public void setRoot(HeroNode root) {
		this.root = root;
	}
	
	//定义节点
	class HeroNode{
		private int id;
		private String name;
		private HeroNode left;
		private HeroNode right;
		public HeroNode(int id,String name){
			this.id = id;
			this.name = name;
		}
		
		public int getId() {
			return id;
		}
		
		public void setId(int id) {
			this.id = id;
		}
		
		public String getName() {
			return name;
		}
		
		public void setName(String name) {
			this.name = name;
		}
		
		public HeroNode getLeft() {
			return left;
		}
		
		public void setLeft(HeroNode left) {
			this.left = left;
		}
		
		public HeroNode getRight() {
			return right;
		}
		
		public void setRight(HeroNode right) {
			this.right = right;
		}
		
		@Override
		public String toString() {
			return "HeroNode{" +
					"id=" + id +
					", name='" + name + '\'' +
					'}';
		}
		
		/*
		 * 遍历二叉树的思路:
		 * 		在节点类内部遍历时前序遍历是先遍历父节点,由于是对象调用方法
		 * 	所以不用判断为空
		 * 		1.当要遍历二叉树时,我们仅知道一个根节点root,要从root节点遍历的话
		 * 	我们都知道二叉树有两个分支,一个left一个right,如果我获取left的话那个right
		 * 	节点就无法遍历,所以这里的思想还是一样的,分成左右依次递归
		 * 		2.由于每次递归要么是左节点要么是右节点,在下一次递归时左节点变成了根节点
		 * 	所以只需要有一个打印就可以了,在递归的过程中会遍历到每个节点
		 * 		3.那么什么时候可以递归,什么时候不可以递归呢,在向左递归时,left节点不为空
		 * 	就可以继续递归,否则跳过,由于每个节点都可能有右节点,所以在左递归时不能进行return
		 * 	因为要用到每次递归的节点,且那些节点可能有右节点
		 * 		4.至于前序,中序,后序遍历是打印节点的位置不同
		 */
		//前序遍历
		public void listqian(){
			System.out.println(this);
			if (this.left != null){
				this.left.listqian();
			}
			if (this.right != null){
				this.right.listqian();
			}
		}
		//中序遍历
		public void listzhong(){
			if (this.left != null){
				this.left.listzhong();
			}
			System.out.println(this);
			if (this.right != null){
				this.right.listzhong();
			}
		}
		//后序遍历
		public void listhou(){
			if (this.left != null){
				this.left.listhou();
			}
			if (this.right != null){
				this.right.listhou();
			}
			System.out.println(this);
		}
		
		/*
		 * 对于无序二叉树的查找:
		 * 		1.对于无序的二叉树进行查找时,只能将整个二叉树进行遍历,将每个
		 * 	节点进行比对才能知道是否是查找的那个节点
		 * 		2.这样的话就需要上面的遍历以及获取返回值,首先判断this.id == id
		 * 	相等的话,直接返回this节点,就是要查找的节点
		 * 		3.然后进行左递归,但这里需要注意的是如果直接return 左递归
		 * 	的话,那么整个递归就不会遍历整个二叉树了,为了不影响遍历整个二叉树,我们需要
		 * 	一个变量来接收左递归的返回值,然后判断这个返回值如果不为空的话就表示
		 * 	找到了该节点,为null的话还需要继续右递归才可,同样使用变量来接收右递归的
		 * 	返回值,但这时不再判断返回值是否为空,直接进行返回,因为右递归同样返回null的话
		 * 	就表示没有找到,直接将null返回即可
		 */
		//前序查找
		public HeroNode findqian(int id){
			if (this.id == id){
				return this;
			}
			HeroNode hero = null;
			if (this.left != null){
				hero = this.left.findqian(id);
			}
			if (hero != null){
				return hero;
			}
			if (this.right != null){
				hero = this.right.findqian(id);
			}
			return hero;
		}
		
		//中序查找
		public HeroNode findzhong(int id){
			HeroNode hero = null;
			if (this.left != null){
				hero = this.left.findzhong(id);
			}
			if (this.id == id){
				return this;
			}
			if (hero != null){
				return hero;
			}
			if (this.right != null){
				hero = this.right.findzhong(id);
			}
			return hero;
		}
		
		//后序查找
		public HeroNode findhou(int id){
			HeroNode hero = null;
			if (this.left != null){
				hero = this.left.findhou(id);
			}
			if (hero != null){
				return hero;
			}
			if (this.right != null){
				hero = this.right.findhou(id);
			}
			if (this.id == id){
				return this;
			}
			return hero;
		}
		
		/*
		 * 删除节点时判断当前节点的left不为空并且id就是需要删除的id时
		 * 将this.left置为空即可
		 * 同样的右分支也是一样的
		 * 然后分别进行左递归与右递归
		 */
		public void del(int id){
			if (this.left != null && this.left.id == id){
				this.left = null;
				return;
			}
			if (this.right != null && this.right.id == id){
				this.right = null;
				return;
			}
			
			if (this.left != null){
				this.left.del(id);
			}
			if (this.right != null){
				this.right.del(id);
			}
		}
	}
}

//线索化二叉树
class LineHeroTree{
	private HeroNode root;//根节点
	//pre表示线索化时递归的上一个节点
	private HeroNode pre;
	//遍历时记录上个节点
	
	//遍历中序线索化二叉树
	/*
	 * 该方法仅适用于中序线索化的二叉树
	 * 在中序线索化时头和尾的节点对应的线索都为null
	 * 而开头一定是一个线索化的节点,根据其特性进行线索化遍历
	 */
	public void listLineTreeZhong(){
		//首先获取根节点
		HeroNode node = root;
		//由于结尾的线索节点为null,随意判断node为null时结束循环
		while (node != null){
			/*
			 * 第一个节点一定是一个线索化的节点
			 * 所以一直判断node.leftType == 0,当leftType不为0时
			 * 就表示找到了那个节点,退出了循环
			 * 这里的代码还有一个作用就是当此循环结束时,node节点的left
			 * 就不需要再进行判断了,因为已经判断过了,而且在后面的节点中
			 * 如果某个节点的left节点是一个子节点的话同样会进行判断
			 */
			while (node.leftType == 0){
				node = node.left;
			}
			//打印该节点
			System.out.println(node);
			/*
			 * 上面找到的一定是一个被线索化的节点,而下一个需要打印的就是
			 * 该节点的后继节点也就是该节点的right节点,但该节点的right节点
			 * 不一定就是后继节点,只能说后继节点在该节点的right子接点中
			 * 所以需要判断,该节点的rightType是否为1,为1的话表示node.right
			 * 节点就是node的后继节点,将其打印,如果不是的话,node.right可能是
			 * 一个子节点(因为能线索化的二叉树,必然是一个完全二叉树)
			 */
			while (node.rightType == 1){
				node = node.right;
				System.out.println(node);
			}
			/*
			 * 在上面的循环之后,可能会进入循环获取到后继节点的下一个节点,
			 * 而该节点不是后继节点,所以不能打印,这里将此节点当做一个普通的节点看待
			 * 但整个代码是从左到右遍历的,经过上面的代码左侧的已经被遍历完毕了
			 * 所以需要获取该节点的right节点,来进行下一次的判定
			 */
			node = node.right;
		}
	}
	
	//遍历中序线索化二叉树
	/*
	 * 该方法仅适用于中序线索化的二叉树
	 * 在中序线索化时头和尾的节点对应的线索都为null
	 * 而开头一定是一个线索化的节点,根据其特性进行线索化遍历
	 */
	public void listLineTreeQian(){
		//定义一个变量，存储当前遍历的结点，从root开始
		HeroNode node = root;
		//由于结尾的线索节点为null,随意判断node为null时结束循环
		while ( node != null ) {
			while ( node.getLeftType() == 0 ) {
				//如果是叶子节点，非前驱节点，打印当前这个结点
				System.out.println(node);
				node = node.getLeft();
			}
			System.out.println(node);
			//替换这个遍历的结点
			node = node.getRight();
		}
	}
	
	public void listLineTreeHou(){
		//1、找后序遍历方式开始的节点
		HeroNode node = root;
		while ( node != null && node.getLeftType() == 0 ) {
			node = node.getLeft();
		}
		while ( node != null ) {
			//右节点是线索
			if (node.getRightType() == 1) {
				System.out.println(node);
				pre = node;
				node = node.getRight();
			} else {
				//如果上个处理的节点是当前节点的右节点
				if (node.getRight() == pre) {
					System.out.println(node);
					if (node == root) {
						return;
					}
					pre = node;
					node = node.getParent();
				} else {    //如果从左节点的进入则找到有子树的最左节点
					node = node.getRight();
					while ( node != null && node.getLeftType() == 0 ) {
						node = node.getLeft();
					}
				}
			}
		}
	}
	
	//二叉树转线索化二叉树
	public void toLineTree(HeroNode hero,int type){
		/*
		 * 在这里分成两个方向分析:
		 * 		1.如果hero当前递归节点为null,表示左递归或者右递归已经到了最后,
		 * 	下面已经没有元素了,这时需要进行return,不再继续执行
		 * 		2.当type为1时表示该节点是一个线索化节点,而线索化的节点不能再继续
		 * 	递归,不然会死归(因为指向的节点是上一个节点,而上一个节点是有子节点的,
		 * 	这样就会不断的去进行递归,形成死归),且已经线索化的节点就处于底层,所以
		 * 	当当前节点为线索化节点时也不再继续执行
		 * 		判断type == 1的情况主要是为了在前序线索化时,是先将节点的left节点
		 * 	设置成了上一个节点,而在下面又进行左递归,这时就出现问题了,假设节点2的
		 * 	左节点为1,第一次对节点2递归时是节点2.left进行递归,进入递归后判断节点1
		 * 	的left为null,将上一个节点,也就是节点2赋给了节点1的left,在下面又左递归,
		 * 	这时的节点1.left就是节点2这样就形成了死归
		 * 		而中序和后序的线索化二叉树没有这种情况,可能有人会想中序线索化也能死归啊,
		 * 	毕竟先设置的right节点,在进行的右递归,但在当前节点的递归中,只会设置left节点
		 * 	而right节点是在下一次递归时,当前节点作为了上一个节点进行设置的,所以在当前节点
		 * 	进行右递归时,right还没有被设置值,所以不会出现前序线索化的问题,同样后序线索化
		 * 	也不会出现,因为是先进行的递归而后才设置的值
		 */
		if (hero == null || type == 1){
			return;
		}
		
		//-------------------前中后序线索化变化位置的代码段:开 始----------------------
		/*
		 * 在这里需要将当前节点的left指向前驱节点
		 * 这里的意思是:
		 * 		找到左节点为null的节点,那么此节点就是需要设置前驱和后继
		 * 	的节点,首先设置前驱,因为pre总是指向递归的上一个节点,
		 * 	那么前驱刚好就是pre,在将leftType设置为1即可
		 */
		if (hero.left == null){
			hero.left = pre;
			hero.leftType = 1;
		}
		/*
		 * 在这里进行设置后继节点,但需要注意的是,二叉树的指针方向是单向的
		 * 当我们递归到当前节点时,我们根本不知道下一次递归的节点到底是哪个节点,
		 * 所以在这里进行了判断,由于pre总是指向递归的上一个节点,所以刚好可以知道
		 * 上次递归的节点就是pre,而它的后继节点就是当前的节点hero,由于pre被初始化
		 * 为null,所以只有不为null时,才表示pre记录了节点,故而将pre的right
		 * 设置为当前的节点hero,就设置完成了后继节点
		 */
		if (pre != null && pre.right == null){
			pre.right = hero;
			pre.rightType = 1;
		}
		//当结束时,把pre指向hero,pre的指针进行后移
		pre = hero;
		//-------------------前中后序线索化变化位置的代码段:结 束------------------------
		
		//左递归
		toLineTree(hero.left,hero.leftType);
		
		
		//右递归
		toLineTree(hero.right,hero.rightType);
	}
	
	public HeroNode getRoot() {
		return root;
	}
	
	public void setRoot(HeroNode root) {
		this.root = root;
	}
	
	//定义节点
	class HeroNode{
		private int id;
		private String name;
		private HeroNode left;
		private HeroNode right;
		private int leftType;//左节点的类型,0:表示指向了左子树 1:表示指向了前驱节点
		private int rightType;//右节点的类型,0:表示指向了右子树 1:表示指向了后继节点
		private HeroNode parent;//此属性是专门为了后序线索化遍历设置的,存储该节点的父节点
		
		public HeroNode getParent() {
			return parent;
		}
		
		public void setParent(HeroNode parent) {
			this.parent = parent;
		}
		
		public HeroNode(int id, String name){
			this.id = id;
			this.name = name;
		}
		
		public int getId() {
			return id;
		}
		
		public void setId(int id) {
			this.id = id;
		}
		
		public String getName() {
			return name;
		}
		
		public void setName(String name) {
			this.name = name;
		}
		
		public HeroNode getLeft() {
			return left;
		}
		
		public void setLeft(HeroNode left) {
			this.left = left;
		}
		
		public HeroNode getRight() {
			return right;
		}
		
		public void setRight(HeroNode right) {
			this.right = right;
		}
		
		public int getLeftType() {
			return leftType;
		}
		
		public HeroNode setLeftType(int leftType) {
			this.leftType = leftType;
			return this;
		}
		
		public int getRightType() {
			return rightType;
		}
		
		public HeroNode setRightType(int rightType) {
			this.rightType = rightType;
			return this;
		}
		
		@Override
		public String toString() {
			return "HeroNode{" +
					"id=" + id +
					", name='" + name + '\'' +
					'}';
		}
	}
}

